package leetcode.editor.cn.q1_300.q50;

import java.util.HashMap;
import java.util.Map;

/**
 * 思路没错，就是超时了。。。
 *
 * @author qidi
 * @date 2021-12-23 14:36:30
 */
class Q0087_ScrambleString_bak {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isScramble(String s1, String s2) {

            if (s1.length() == 1) return s1.equals(s2);

            if (s1.length() != s2.length()) return false;

            Map<Character, Integer> map1 = new HashMap<>();
            Map<Character, Integer> map2 = new HashMap<>();

            for (int i = 0; i < s1.length(); i++) {
                char c1 = s1.charAt(i);
                Integer num1 = map1.getOrDefault(c1, 0);
                map1.put(c1, num1 + 1);

                char c2 = s2.charAt(i);
                Integer num2 = map2.getOrDefault(c2, 0);
                map2.put(c2, num2 + 1);
            }

            if (!checke(map1, map2)) return false;

            return process(s1, s2);
        }

        private boolean process(String s1, String s2) {
            if (s1.length() == 1) return s1.equals(s2);

            Map<Character, Integer> map1 = new HashMap<>();
            Map<Character, Integer> map2 = new HashMap<>();
            Map<Character, Integer> map3 = new HashMap<>();

            int len = s1.length();
            for (int i = 0; i < len - 1; i++) {
                char c1 = s1.charAt(i);
                Integer num1 = map1.getOrDefault(c1, 0);
                map1.put(c1, num1 + 1);

                char c2 = s2.charAt(i);
                Integer num2 = map2.getOrDefault(c2, 0);
                map2.put(c2, num2 + 1);

                char c3 = s2.charAt(len - 1 - i);
                Integer num3 = map3.getOrDefault(c3, 0);
                map3.put(c3, num3 + 1);

                if (checke(map1, map2)) {
                    if (process(s1.substring(0, i + 1), s2.substring(0, i + 1)) && process(s1.substring(i + 1), s2.substring(i + 1))) {
                        return true;
                    }
                }
                if (checke(map1, map3)) {
                    if (process(s1.substring(0, i + 1), s2.substring(len - i - 1)) && process(s1.substring(i + 1), s2.substring(0, len - i - 1))) {
                        return true;
                    }
                }
            }

            return false;
        }

        private boolean checke(Map<Character, Integer> map1, Map<Character, Integer> map2) {
            for (Map.Entry<Character, Integer> entry : map1.entrySet()) {
                if (entry.getValue() != map2.get(entry.getKey())) return false;
            }
            return true;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0087_ScrambleString_bak().new Solution();
        System.out.println(solution.isScramble("eebaacbcbcadaaedceaaacadccd", "eadcaacabaddaceacbceaabeccd"));
        System.out.println(solution.isScramble("abcdbdacb", "bdacabcdb"));
        System.out.println(solution.isScramble("abcdbdacbdac", "bdacabcdbdac"));
        System.out.println(solution.isScramble("dbdac", "abcdd"));
        System.out.println(solution.isScramble("abb", "bab"));
        System.out.println(solution.isScramble("abc", "cab"));
        System.out.println(solution.isScramble("ab", "ba"));
        System.out.println(solution.isScramble("abcd", "bdac"));
        System.out.println(solution.isScramble("abcde", "aecdb"));
        System.out.println(solution.isScramble("abcde", "caebd"));
    }
}